package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no84;

import cn.hutool.core.date.StopWatch;
import cn.hutool.core.io.FileUtil;
import cn.hutool.json.JSONUtil;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String content = FileUtil.readUtf8String("E:/test/no84.txt");
        int[] height = {2, 1, 5, 6, 2, 3, 1};
        height = JSONUtil.toList(content, Integer.class).stream().mapToInt(Integer::intValue).toArray();
//        height = new int[]{2, 3};
        StopWatch stopWatch = new StopWatch();
        stopWatch.start();
        System.out.println(solution.largestRectangleArea(height));
        stopWatch.stop();
        System.out.println(stopWatch.prettyPrint());
        System.out.println(stopWatch.getTotalTimeMillis());
//        System.out.println(solution.largestRectangleArea2(height));

    }

    public int largestRectangleArea2(int[] heights) {
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            int len = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (heights[j] >= heights[i]) {
                    len++;
                } else {
                    break;
                }
            }

            for (int j = i + 1; j < heights.length; j++) {
                if (heights[j] >= heights[i]) {
                    len++;
                } else {
                    break;
                }
            }
            int area = len * heights[i];
            if (area > max) {
                max = area;
            }
        }
        return max;
    }


    public int largestRectangleArea(int[] heights) {
        int max = 0;
        int[] dp = new int[heights.length];
        int[] dp2 = new int[heights.length];
        for (int i = 1; i < heights.length; i++) {
            if (heights[i - 1] >= heights[i]) {
                dp[i] = dp[i - 1];
                while (dp[i] >= 0) {
                    if (dp[i] - 1 >= 0) {
                        if (heights[i] <= heights[dp[i] - 1]) {
                            dp[i] = dp[dp[i] - 1];
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
            } else {
                dp[i] = i;
            }
        }
        int mLen = heights.length - 1;
        dp2[mLen] = mLen;
        for (int i = mLen - 1; i >= 0; i--) {
            if (heights[i + 1] >= heights[i]) {
                dp2[i] = dp2[i + 1];
                while (dp2[i] <= mLen) {
                    if (dp2[i] + 1 <= mLen) {
                        if (heights[i] <= heights[dp2[i] + 1]) {
                            dp2[i] = dp2[dp2[i] + 1];
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
            } else {
                dp2[i] = i;
            }
        }
        for (int i = 0; i < heights.length; i++) {
            int area = (dp2[i] - dp[i] + 1) * heights[i];
            if (area > max) {
                max = area;
            }
        }
        return max;
    }
}
